import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author ZhengDp
 * @Date 2023/4/25 17:03
 */
public class 排序 {
    /*
    * #problem 1122 数组的相对排序
    * */
    // 1.桶排序
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] count = new int[1001];
        for(int i =0;i<arr1.length;i++) {
            count[arr1[i]] ++;
        }
        int i =0,j=0;
        while(i<arr2.length) {
            int num = arr2[i];
            for(int k = 0;k<count[num];k++) {
                arr1[j++] = num;
            }
            count[num] = 0;
            i++;
        }
        for(int num = 0;num<count.length;num++) {
            int sum = count[num];
            if(sum != 0) {
                while(sum -- >0) {
                    arr1[j++] = num;
                }
            }
        }
        return arr1;
    }

    /*
    * #problem 242 有效的字母异位词
    * */
    // 1. 桶排序
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }
        int[] count = new int[26];
        for(int i =0;i<s.length();i++) {
            char cs = s.charAt(i);
            char ts = s.charAt(i);
            count[cs-'a'] ++;
            count[ts-'a']--;
        }
        for(int num : count) {
            if(num != 0) {
                return false;
            }
        }
        return true;
    }

    /*
    * #problem 56 合并区间
    * */
    // 1. 对左区间进行升序排序，==> 可以合并的区间一定会是连续的
    public int[][] merge(int[][] intervals) {
         List<int[]> arr = new ArrayList<>();
         for(int[] t : intervals) {
             arr.add(t);
         }
         arr.sort((o1, o2) -> o1[0] - o2[0]);
        Deque<int[]> stack = new LinkedList<>();
        for(int i =0;i<arr.size();i++) {
            int[] cur = arr.get(i);
            if(stack.isEmpty()) {
                stack.push(cur);
            } else {
                int[] peek = stack.peek();
                if(peek[1] < cur[0]) {
                    stack.push(cur);
                } else {
                    int[] pop = stack.pop();
                    pop[0] = peek[0];
                    pop[1] = Math.max(pop[1],cur[1]);
                    stack.push(pop);
                }
            }
        }
        int[][] res = new int[stack.size()][2];
        int i =stack.size()-1;
        while(!stack.isEmpty()) {
            res[i--] = stack.pop();
        }
        return res;
    }

    /*
    * #problem 493 翻转对
    * */
    @Test
    void test(){
        System.out.println(reversePairsII(new int[]{1,3,2,3,1}));
    }
    // 1. 类似逆序对？ 使用归并排序
    public int reversePairsII(int[] nums) {
        return mergeSortII(nums,0,nums.length-1);
    }

    private int mergeSortII(int[] nums, int left, int right) {
        if(left >= right) {
            return 0;
        }
        int mid = (right - left) /2 + left;
        int res = mergeSortII(nums,left,mid);
        res += mergeSortII(nums,mid+1,right);
        res += mergeII(nums,left,mid,right);
        return res;
    }

    private int mergeII(int[] nums,int left,int mid,int right) {
        int[] temp = new int[right-left+1];
        int index = 0,i = left,j=mid+1;
        int count = 0;
        // 先统计，再合并
        // 判断当前i下标有多少个符合条件的翻转对
        while(i<= mid) {
            // [left,mid] 单调递增，如果i-1跟 [mid+1,j]之间的数可以成为逆序对，那么i+1一定也可以
            while(j<= right && (long)nums[i] > (long)2*nums[j]) {
                j++;
            }
            count += j-mid-1;
            i++;
        }
        i = left;j = mid+1;
        while(i<=mid && j <= right) {
            if(nums[i] > nums[j]) {
                temp[index] = nums[j++];
            } else {
                temp[index] = nums[i++];
            }
            index++;
        }
        while(i<= mid) {
            temp[index++] = nums[i++];
        }
        while(j<= right)  {
            temp[index++] = nums[j++];
        }
        for(int k =0;k<temp.length;k++) {
            nums[left++] = temp[k];
        }
        return count;
    }

    /*
    * #problem 剑指 Offer 51. 数组中的逆序对
    * */
    // 1. 归并排序，在merge的时候进行逆序对的统计
    public int reversePairs(int[] nums) {
        return mergeSort(nums,0,nums.length-1);
    }

    private int mergeSort(int[] nums,int left,int right) {
        if(left >= right) {
            return 0;
        }
        int mid = (right - left) /2 + left;
        int res =0;
        res = mergeSort(nums,left,mid);
        res += mergeSort(nums,mid+1,right);
        res += merge(nums,left,mid,right);
        return res;
    }

    private int merge(int[] nums,int left,int mid,int right) {
        int count = 0;
        // [left,mid] 的下标x肯定小于 [mid+1,right] 的下标y
        // 所以当 nums[x] > nums[y] 时，组成一个逆序对
        int i = left, j = mid+1;
        int[] temp = new int[right-left+1];
        int index = 0;
        while(i<= mid && j <= right) {
            if(nums[i] > nums[j]) {
                count += mid-i+1;
                temp[index] = nums[j++];
            } else {
                temp[index] = nums[i++];
            }
            index++;
        }
        while(i<= mid) {
            temp[index++]  = nums[i++];
        }
        while(j<= right) {
            temp[index++] = nums[j++];
        }
        for(index =0;index<temp.length;index++) {
            nums[left++] = temp[index];
        }
        return count;
    }


}
/*
 * #problem 1244 力扣排行榜
 * */
class Leaderboard {

    private Map<Integer,Node> memo;
    private Node head;
    private Node tail;

    public Leaderboard() {
        memo = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    /*
    * - 假如参赛者已经在排行榜上，就给他的当前得分增加score点分值，并更新排行
    * - 假如该参赛者不在排行榜上，就把它添加到榜单上，并且将分数设置为`score`
    * */
    public void addScore(int playerId, int score) {
        Node node = memo.get(playerId);
        boolean isExist = false;
        if(node != null) {
            isExist = true;
            node.val += score;
        } else {
            isExist = false;
            node = new Node(playerId,score);
        }
        addScore(node,isExist);

    }


    private void addScore(Node node,boolean isExist) {
        Node t = tail.prev;
        if(isExist) {
            t = node.prev;
            // 将node结点从链表中删除
            reset(node.key);
        }
        while(t != head) {
            if(t.val >= node.val) {
                break;
            } else {
                t = t.prev;
            }
        }
        node.next = t.next;
        node.prev = t;
        node.next.prev = node;
        node.prev.next = node;
        memo.put(node.key,node);
    }

    /*
    * 返回前K名参赛者的 **得分总和**
    * */
    public int top(int K) {
        Node h = head.next;
        int count = 0;
        while(K-- >0 && h != tail) {
            count += h.val;
            h = h.next;
        }
        return count;
    }

    /*
    * 将指定参赛者的成绩清零（将其从排行榜中删除）
    * */
    public void reset(int playerId) {
        Node node = memo.get(playerId);
        if(node != null) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = null;
            node.prev = null;
            memo.remove(playerId);
        }
    }

    private class Node {
        int val;
        int key;
        Node next,prev;
        public Node(int key,int value) {
            this.val = value;
            this.key = key;
        }

        public Node(){}
    }
}
